#include "AStarVarPancake.h"

#include <time.h>
#include <stdio.h>                                   
#include <stdlib.h>                                  
#include <math.h>
#include <stdio.h>
#include <iostream>
#include <iostream>
#include <string.h>
#include <sstream>
#include <queue>
using namespace std;

// ------------------------------------------------
//                  Parameters
//-------------------------------------------------
const long MAX_HASH = 20000000;                              /*max size of memory (hash table)*/
const long FULL_OPEN = 19100000;                            /* max size of open list */

bool OperMat[SIZE+1][SIZE];/* Do we need it? Probably not - Allowed operation table*/
bool DEBUG_PRINTS=true;
bool PerformTrivial=true;
bool UseInconsistency=true;
//---------- Hash table definitions (total memory) --------------
 struct hashtable                                 /* table of generated states */
{                            
 short boardState[SIZE];
 short g;                                      /* distance from initial state */
 short h;                        /* static heuristic distance from goal state */
 short PrevMove;                                /* previous position of blank */
 int link;                    /* pointer to next element with same hash value */
 int heaplink;
 int cost;
 // TODO - check if the prev and next are needed
 //int prev;                            /* index of previous state in open list */
 //int next;
 } old[MAX_HASH];      /* index of next state in open list, last is NIL */

 int bucket[MAX_HASH];   /* pointer to first element in table with given hash value */
 int empty;                      /* index of first free location in hash table */
 unsigned int hashPowers[SIZE][SIZE]; /* supporting vector to calculate hash value*/

 //------------- Heap definitions (total memory) ----------------
 int heap[FULL_OPEN];
int bestf;
int bestc;
int NextBestF;

int OpenStart;         /* index of first element of OPEN list*/
int OpenEnd;			/* index of last element of open list*/


//---------------- PDB definition ------------------------------
UCHAR huristicTable[TABLESIZE]; //holds the PDB in memory
int tilePosForGetH[PATTERNSIZE]; //
int DualState[SIZE];             //Contains the converted state into dual
int arrPatternLocation[SIZE]; //mark the tiles included in the pattern. all the rest are -1
//--------------- BPMX Search support parameters ---------------
//int delta;

//--------------- Counters -------------------------------------
int UpperLimit;                              /* current goal best cost */
int expanded;                               /* total number of nodes expanded */
int generated;                             /* total number of nodes generated */
int stored;                                  /* total number of states stored */
int ImmediateGenerated;                      /* total number of states generated by changing the parent (without allocating mameory)*/
int IE;                                     /* total number of states expanded and entered immediatlly to the close list*/
int reopened;                              /* total number of states that were re-entered from close to open*/
int reclosed;
int goalDepth;                             /* minimum number of steps from initial state to goal*/
int opened;                                /* total number of states entered to open list */
int closed;                                /* total number of states entered to close list */
int maxopen;                               /* maximum size of open list */
int copen;                                 /* supporting counter to determine maxopen*/
int duplicatCounter;                       /* number of states that already exist in memory*/
int CaseCounter;                           /* count the number of problems solved */
int FoundInC;
int FoundInO;
int minf;
int NextBestC;
int LHnodes;
int BUpdate;
int LHUpdate;
int BLHUpdate;
int IGSameV;

int UCount;

double time2search;                        /* timer measuring search time for a single state-problem*/
int CostArr[40];
//***************************************************************************************************/

//------------- General utilities ------------------
void PrintResult2File(string SearchName,int lookahead)
{
	FILE *f1;
		
	f1 = fopen("AStarLH_100_TopSpin16_withSkip.csv","a");
	fprintf(f1,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",lookahead,CaseCounter,expanded,IE,stored,goalDepth,ImmediateGenerated,maxopen,opened,closed,duplicatCounter,reopened,time2search);
	fclose(f1);
}

void PrintResult(int lookahead)
{
	FILE *f1;

	f1=fopen("IBPMX_10Nov_1.csv","a");
	fprintf(f1,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",CaseCounter,lookahead,goalDepth,expanded,IE,stored,ImmediateGenerated,reopened,reclosed,LHnodes,BUpdate,LHUpdate,BLHUpdate,time2search);
	fclose(f1);

}

void PrintResult(char* algorithmName)
{
	FILE *f1;

	f1=fopen("IBPMX_10Nov_1.csv","a");
	fprintf(f1,"%d,%s,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",CaseCounter,algorithmName,goalDepth,expanded,IE,stored,ImmediateGenerated,reopened,reclosed,LHnodes,BUpdate,LHUpdate,BLHUpdate,time2search);
	fclose(f1);

}

void PrintResult(char* algorithmName,int lookahead)
{
	FILE *f1;

	f1=fopen("IBPMX_10Nov_1.csv","a");
	fprintf(f1,"%d,",CaseCounter);
	fprintf(f1,algorithmName,lookahead);
	fprintf(f1,",%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%f\n",goalDepth,expanded,IE,stored,ImmediateGenerated,reopened,reclosed,LHnodes,BUpdate,LHUpdate,BLHUpdate,time2search);
	fclose(f1);

}

I64 CalcHash(short state[SIZE])
{

	I64 val=1;
	I64 tempval;


	for (int i=0;i<SIZE;i++)
	{
		tempval=state[i];
		val+=hashPowers[i][tempval];
	}
	//printf("%u\n",val);
	val=val%MAX_HASH;

	return val;

}

//-------------- State (changing & updaing)---------
// Function name	: MakeMove
// Description	    : This function make move iMove on state in stateIndex
// Return type		: void 
// Argument         : int stateIndex (index of the state in hash)
// Argument         : int iMove

void MakeMove(int stateIndex,int iMove)
{
	int TempTile;
	
	for (int i=0;i<=iMove/2;i++)
	{
		TempTile=old[stateIndex].boardState[i];
		old[stateIndex].boardState[i]=old[stateIndex].boardState[iMove-i];
		old[stateIndex].boardState[iMove-i]=TempTile;
	}

}

void MakeMove(short state[SIZE],int iMove)
{
	int TempTile;

	for (int i=0;i<=iMove/2;i++)
	{
		TempTile=state[i];
		state[i]=state[iMove-i];
		state[iMove-i]=TempTile;
	}

}

// Function name	: ConvertStateToDual
// Description	    : This function make update DualState array with the locations of the tiles (for H calculations)
// Return type		: void 
// Argument         : int stateIndex (index of the state in hash)
void ConvertStateToDual(int stateIndex)
{
	if (UseInconsistency){	
		for (int i=0;i<SIZE;i++)
		{
			DualState[old[stateIndex].boardState[i]]=i;
		}
	}
	else{
		for (int i=0;i<SIZE;i++)
		{
			DualState[i]=old[stateIndex].boardState[i];
		}
	}
}
void ConvertStateToDual(short state[SIZE])
{
	if (UseInconsistency){
		for (int i=0;i<SIZE;i++)
		{
			DualState[state[i]]=i;
		}
	}
	else{
		for (int i=0;i<SIZE;i++)
		{
			DualState[i]=state[i];
		}
	}



}
void ConvertStateToDual(int stateIndex, int out_DualState[SIZE])
{

	for (int i=0;i<SIZE;i++)
	{
		out_DualState[old[stateIndex].boardState[i]]=i;
	}
}

// Function name	: IsGoal
// Description	    : This function make checks if the state answers the goal conditions (0,1,2,3,4,5,6,7...)
// Return type		: bool 
// Argument         : int stateIndex (index of the state in hash)
bool IsGoal(int stateIndex)
{
	bool GoalTest=true;

	for (int i=0;i<SIZE;i++)
	{
		if(old[stateIndex].boardState[i]!=i) GoalTest=false;
	}

	return GoalTest;
}

bool IsGoal(int state[SIZE])
{
	bool GoalTest=true;

	for (int i=0;i<SIZE;i++)
	{
		if(state[i]!=i) GoalTest=false;
	}

	return GoalTest;
}
bool IsGoal(short state[SIZE])
{
	bool GoalTest=true;

	for (int i=0;i<SIZE;i++)
	{
		if(state[i]!=i) GoalTest=false;
	}

	return GoalTest;
}

//-------------- PDB (uploading and using)----------
// Function name	: InitPDB
// Description	    : This function uploads the PDB to memory 
//                    from a PDB file (name and path specified in AStarVarPancake.h)
// Return type		: void 
void InitPDB()
{
	FILE *infile;

	// Open the PDB file
	printf("Reading PDB - %s\n",FILE1);
	infile = fopen(FILE1,"rb");

		// If file doen't exist - exit
	if (infile == NULL)
	{
		printf("Can't locate PDB...\n");
		exit(0);
	}

	// Read the file into huristicTable
	fread(huristicTable,sizeof(UCHAR)*TABLESIZE,1,infile);
	fclose(infile);
}


// Function name	: InitPDBParameters
// Description	    : This function analyses the tile of the PDB based on the PDB file name
//                    from a PDB file (name and path specified in AStarVarPancake.h)
// Return type		: void 
void InitPDBParameters()
{
	int number1;
	int PatArray[PATTERNSIZE];
	char *token;
	char name[100];


	strcpy(name,FILE1);
	token = strtok(name,"_");
	token = strtok(NULL,"_");
	int acc =0;
	while(token)
	{
		PatArray[acc] = atoi(token);
		token = strtok(NULL,"_");
		acc++;
	}

	for (int i = 0; i < SIZE; i++)
		arrPatternLocation[i] = -1;
    acc =0;
	for (int i=0;i<PATTERNSIZE;i++)
	{
		number1 = PatArray[i];
		arrPatternLocation[number1] = acc;
		acc++;
	}

}

// Function name	: ConvarteStateToTilesPos
// Description	    : This function finds the locations of the PDB tiles of the specific state 
//                    for heuristic calc purposes
//                    Example (for PDB size=11)
//                    state: 1 7 5 8 4 3 9 1 10 6 2 0
//                    arrPtternLocation: -1 -1 -1 -1 0 1 2 3 4 5 6 
//                    tilePosForGetH: 4 2 9 1 3 6 8 (the locations of tiles 4 - 10 in the state)
// Return type		: void 
void ConvarteStateToTilesPos(int stateIndex)
{
	int tile;

	for (int i=0;i<PATTERNSIZE;i++)
		tilePosForGetH[i]=-1;

	for (int i=0;i<SIZE;i++)
	{
		tile=old[stateIndex].boardState[i];
		if(arrPatternLocation[tile]!=-1)
			tilePosForGetH[arrPatternLocation[tile]]=i;
	}
}

void ConvarteStateToTilesPos(int RegularState[SIZE])
{
	int tile;

	for (int i=0;i<PATTERNSIZE;i++)
		tilePosForGetH[i]=-1;

	for (int i=0;i<SIZE;i++)
	{
		tile=RegularState[i];
		if(arrPatternLocation[tile]!=-1)
			tilePosForGetH[arrPatternLocation[tile]]=i;
	}
}

// will be calculated based on tilePosForGetH
I64 hash()
{
	int i,digit,j;
	I64 hashval = 0;
	for (i = 0; i < PATTERNSIZE ; i++)                         /* for each remaining position in permutation */
    {digit = tilePosForGetH[i] ;                                  /* initially digit is value in permutation */
      for (j = 0; j < i; j++)                           /* for each previous element in permutation */
       if (tilePosForGetH[j] < tilePosForGetH[i]) digit--; /* previous position contains smaller value, decrement digit*/
         hashval = hashval * (SIZE - i) + digit;}              /* multiply digit by appropriate factor */
	return hashval;
}


// Function name	: GetHuristicRegular
// Description	    : This function calculates the heuristic value
// Argument         : int stateIndex (index of the state in hash)
// Return type		: int 
int GetHuristicRegular(int stateIndex)
{
	I64 hashVal;
	int val;

	ConvarteStateToTilesPos(stateIndex);// now the tilePosForGetH array is updated
	hashVal=hash();
	
	val=huristicTable[hashVal];

	return val;
}

int GetHuristicRegular(int state[SIZE])
{
	I64 hashVal;
	int val;

	ConvarteStateToTilesPos(state);// now the tilePosForGetH array is updated
	hashVal=hash();
	
	val=huristicTable[hashVal];

	return val;
}

//----- Heap activities (hash, insert, delete) --------
void FHeapify(int iloc)
{
	int right;
	int left;

	int rightf;
	int rightc;
	int rightg;

	int leftf;
	int leftc;
	int leftg;

	int itemf;
	int itemc;
	int itemg;

	int minCost=iloc;

	right=2*iloc+2;
	left=2*iloc+1;


	itemf=old[heap[iloc]].g+old[heap[iloc]].h;
	itemc=old[heap[iloc]].cost;
	itemg=old[heap[iloc]].g;


	if(right<= OpenStart)
	{
		rightf=old[heap[right]].g+old[heap[right]].h;
		rightc=old[heap[right]].cost;
		rightg=old[heap[right]].g;
		
		
	}
	if (left<=OpenStart)
	{
		leftf=old[heap[left]].g+old[heap[left]].h;
		leftc=old[heap[left]].cost;
		leftg=old[heap[left]].g;
		

	}


	//if(left<=OpenStart && (leftc<itemc || (itemc==leftc && leftf<=itemf)))
	if(left<=OpenStart && (leftc<itemc || (itemc==leftc && leftf<itemf) ||(itemc==leftc && leftf==itemf && leftg>=itemg )))
	{
		minCost=left;
	}
	else
	{
		minCost=iloc;
	}
	//if(right<=OpenStart  && (rightc<old[heap[minCost]].cost || (old[heap[minCost]].cost==rightc && rightf<=old[heap[minCost]].g+old[heap[minCost]].h)))
	if(right<=OpenStart  && (rightc<old[heap[minCost]].cost || (old[heap[minCost]].cost==rightc && rightf<old[heap[minCost]].g+old[heap[minCost]].h) || (old[heap[minCost]].cost==rightc && rightf==old[heap[minCost]].g+old[heap[minCost]].h && rightg>=old[heap[minCost]].g)))
	{
		minCost=right;
	}

		if(minCost!=iloc)
		{
			old[heap[iloc]].heaplink=minCost;
			old[heap[minCost]].heaplink=iloc;
			int temp=heap[iloc];
			heap[iloc]=heap[minCost];
			heap[minCost]=temp;
			FHeapify(minCost);
		}


}
void FHeapify_up(int iloc)
{
	int parent;
	int parentc;
	int parentg;
	int parentf;
	int child;
	int childg;
	int childc;
	int childf;


	parent=floor((double)(iloc-1)/2);
	parentg=old[heap[parent]].g;
	parentf=parentg+old[heap[parent]].h;
	parentc=old[heap[parent]].cost;

	child=iloc;
	childg=old[heap[child]].g;
	childc=old[heap[child]].cost;
	childf=old[heap[child]].g+old[heap[child]].h;

	if(parent<0) 
	{
	
		return;
	}
	//if(parentc>childc || (parentc==childc && childf<=parentf))
	if(parentc>childc || (parentc==childc && childf<parentf) || (parentc==childc && childf==parentf && childg>=parentg))//)
	{
		
		int temp=heap[parent];
		old[heap[parent]].heaplink=child;
		old[heap[child]].heaplink=parent;
		heap[parent]=heap[child];
		heap[child]=temp;
		
		FHeapify_up(parent);
	}


}


void Heapify_up(int iloc)
{
	int parent;
	int parentg;
	int parentf;
	int child;
	int childg;
	int childf;

	parent=floor((double)(iloc-1)/2);
	parentg=old[heap[parent]].g;
	parentf=parentg+old[heap[parent]].h;

	child=iloc;
	childg=old[heap[child]].g;
	childf=old[heap[child]].h+childg;

	if(parent<0) return;
	if(parentf>childf || (parentf==childf && childg>=parentg))
	{
		
		int temp=heap[parent];
		old[heap[parent]].heaplink=child;
		old[heap[child]].heaplink=parent;
		heap[parent]=heap[child];
		heap[child]=temp;
		
		Heapify_up(parent);
	}

}

void Heapify(int iloc)
{
	int right;
	int left;

	int rightf;
	int rightg;

	int leftf;
	int leftg;

	int itemf;
	int itemg;

	int minCost=iloc;

	right=2*iloc+2;
	left=2*iloc+1;


	itemf=old[heap[iloc]].g+old[heap[iloc]].h;
	itemg=old[heap[iloc]].g;

	if(right<= OpenStart)
	{
		rightf=old[heap[right]].g+old[heap[right]].h;
		rightg=old[heap[right]].g;
		
	}
	if (left<=OpenStart)
	{
		leftf=old[heap[left]].g+old[heap[left]].h;
		leftg=old[heap[left]].g;

	}


	if(left<=OpenStart && (leftf<itemf || (itemf==leftf && leftg>=itemg)))
	{
		minCost=left;
	}
	else
	{
		minCost=iloc;
	}

	if(right<=OpenStart && (rightf<old[heap[minCost]].h+old[heap[minCost]].g || (old[heap[minCost]].h+old[heap[minCost]].g==rightf && rightg>=old[heap[minCost]].g)))
	{
		minCost=right;
	}


		if(minCost!=iloc)
		{
			old[heap[iloc]].heaplink=minCost;
			old[heap[minCost]].heaplink=iloc;
			int temp=heap[iloc];
			heap[iloc]=heap[minCost];
			heap[minCost]=temp;
			Heapify(minCost);
		}


}






//----- Hash activities (hash, insert, delete) --------

// Function name	: initHashPow
// Description	    : This function initialize the supporting vector hashPowers (helps to calculate hash value)
//                    will contain 
// Return type		: void
void initHashPow()
{
	for (int i=0;i<SIZE;i++)
	{
		for (int j=0;j<SIZE;j++)
		{
			hashPowers[i][j]=(unsigned int)(pow((float)SIZE,i)*j);
			//printf("%u ",hashPowers[i][j]);
		}
		//printf("%s\n","");
	}
}




int SearchHash (short state2search[SIZE],int hashval)


{int index;                        /* index to different states in hash table */
 int pos;                            /* index to different positions in state */


 index = bucket[hashval];                     /* first state in target bucket */

 while (index != MAX_HASH)                         /* end of chain not reached yet */
   {
	   for (pos = 0; pos < SIZE; pos++)           /* each position in the state */
      if (state2search[pos] != old[index].boardState[pos]) break;    /* mismatch: exit for loop */
    if (pos == SIZE) return (index);         /* state found, return location */
    else index = old[index].link;}                     /* next state on chain */

 
return (-1);}

void InsertHash (int parentNode,int hashval,int PrevMove, int g, int h)

{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */
	 double copy_startclock;
     double copy_endclock;
	 double insert_startclock;
	 double insert_endclock;

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	for (int i=0;i<SIZE;i++)
	{
		if(old[parentNode].boardState[i]==-2) printf("%s\n","we have an issue");
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	Heapify_up(OpenStart);

    if (f < bestf) bestf = f;

}

void InsertHash2(short state[SIZE],int hashval,int PrevMove, int g, int h)
{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */
	 double copy_startclock;
     double copy_endclock;
	 double insert_startclock;
	 double insert_endclock;

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	Heapify_up(OpenStart);

    if (f < bestf) bestf = f;

}



void FInsertHash2(short state[SIZE],int hashval,int PrevMove, int g, int h,int cost)
{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */
	 double copy_startclock;
     double copy_endclock;
	 double insert_startclock;
	 double insert_endclock;

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	old[index].cost=cost;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	FHeapify_up(OpenStart);

    if (f < bestf) bestf = f;

}



void FInsertHash (int parentNode,int hashval,int PrevMove, int g, int h,int cost)

{
	//int word;                                            /* word in packed state */
	 int f;                                            /* combined merit function - no need - BFS*/
	 int index;                           /* index in hash table where state goes */
	 double copy_startclock;
     double copy_endclock;
	 double insert_startclock;
	 double insert_endclock;

	 index = empty++;           /* store in first empty location , empty defined globaly */
	 stored++;                        /* increment number of states in hash table */
	 opened++;
	 copen++;
	 if(maxopen<copen) maxopen=copen;


	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;
	old[index].cost=cost;
	

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	 
	

	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */
	 f = old[index].g + old[index].h;


		//Heap OPEN list
		
	OpenStart++;

	
	heap[OpenStart]=index;
	old[index].heaplink=OpenStart;
	FHeapify_up(OpenStart);
	//Heapify_up(OpenStart);
	
    if (f < bestf) bestf = f;

}
void FDeleteFromOpenList (int index)
{
	int current;                                      /* current index in search */
    int f;                                     /* F value of state to be deleted */
    int next;                                 /* pointer to next element in list */
	FILE *solution;

 f = old[index].g + old[index].h;       /* compute F value of state */
 closed++;
 copen--;
 ////DELETE from HEAP	
 int ploc=old[index].heaplink;//the parent location in the heap array

 old[index].heaplink=-1;
 //old[index].cost=-1;
 int child;

 if(ploc>OpenStart || ploc<0)
 {
	 //printf("%s\n","No such element");

 }
 else
 {
	 heap[ploc]=heap[OpenStart];
	 old[heap[OpenStart]].heaplink=ploc;
	 OpenStart--;
	FHeapify(ploc);
	 //Heapify(ploc);

 }

}
int FAdd2Close(int parentNode,int hashval,int PrevMove, int g, int h,int cost)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	old[index].cost=cost;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */

return index;
}

int FAdd2Close(short state[SIZE],int hashval,int PrevMove, int g, int h,int cost)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;
	old[index].cost=cost;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */

return index;
}

int Add2Close(int parentNode,int hashval,int PrevMove, int g, int h)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=old[parentNode].boardState[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */

	 return index;

}
int Add2Close(short state[SIZE],int hashval,int PrevMove, int g, int h)
{
	int index;
	
	index = empty++;           /* store in first empty location , empty defined globaly */
	stored++; 
	closed++;
	//IE++;

	for (int i=0;i<SIZE;i++)
	{
		old[index].boardState[i]=state[i];
	}
	old[index].PrevMove=PrevMove;

	//3. update h & g
	old[index].g=g;
	old[index].h=h;


	 //TODO - need to re-think the assigment of the hash list per hashvalue (instead of adding the last node first, add it to the end of the list)
	 old[index].link = bucket[hashval];      /* next pointer to old first element */
	 bucket[hashval] = index;               /* new state is at head of hash chain */

	 return index;

}





void DeleteFromOpenList (int index)
{
	int current;                                      /* current index in search */
    int f;                                     /* F value of state to be deleted */
    int next;                                 /* pointer to next element in list */
	FILE *solution;

 f = old[index].g + old[index].h;       /* compute F value of state */
 closed++;
 copen--;

 ////DELETE from HEAP	
 int ploc=old[index].heaplink;//the parent location in the heap array
 old[index].heaplink=-1;
 int child;

 if(ploc>OpenStart || ploc<0)
 {
	 //printf("%s\n","No such element");

 }
 else
 {
	 heap[ploc]=heap[OpenStart];
	 old[heap[OpenStart]].heaplink=ploc;
	 OpenStart--;
	 Heapify(ploc);

 }

}



//-------------- Search activities --------------------
//-------------- A Star -------------------------------
void FReOpen(int stateIndex, int newg, int PrevMove)
{
	int ReArIndex=-1;

	old[stateIndex].g=newg;
	old[stateIndex].PrevMove=PrevMove;
	ReArIndex=old[stateIndex].heaplink;


	if (old[stateIndex].heaplink==-1)
	{
		opened++;
		 copen++;
		 closed--;

		if(maxopen<copen) maxopen=copen;
		OpenStart++;
		ReArIndex=OpenStart;
		heap[OpenStart]=stateIndex;
		old[stateIndex].heaplink=OpenStart;
	}
	FHeapify_up(ReArIndex);

}
void ReOpen(int stateIndex, int newg, int PrevMove)
{
	int ReArIndex=-1;

	old[stateIndex].g=newg;
	old[stateIndex].PrevMove=PrevMove;
	ReArIndex=old[stateIndex].heaplink;


	if (old[stateIndex].heaplink==-1)
	{
		opened++;
		 copen++;
		 closed--;

		if(maxopen<copen) maxopen=copen;
		OpenStart++;
		ReArIndex=OpenStart;
		heap[OpenStart]=stateIndex;
		old[stateIndex].heaplink=OpenStart;
	}
	Heapify_up(ReArIndex);

}
int HBLookahead3(short state[SIZE],int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;

	rh=0;


	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
			continue;

		MakeMove(state,newMove); //generate a child
		ImmediateGenerated++;

		 ConvertStateToDual(state);
		 newh=GetHuristicRegular(DualState); //calculate child h
		 if(newh+newg<=lookahead && newh==0 && IsGoal(state))
		 {
			 if(newg<UpperLimit) 
				UpperLimit=newg;
			 MakeMove(state,newMove); // Undo
			 continue;
		 }
		
		 if( newg+newh<=lookahead && newg+newh<UpperLimit) // if the child cost is lower than the current goal - perform DFS
		 {
			 newh=HBLookahead3(state,newg,newh,lookahead,newMove);
		 }

		 h=MAX(h,newh-1);

		 MakeMove(state,newMove); // Undo

		 if(newh+newg<minf && newh+newg>lookahead)
		 {			
			 minf=newh+newg;
		 }
		 if(g+h>lookahead)
		 {			
			 return h;
		 } 		 
	}//end for	
return h;
}//End BLookahead

int HBLookahead3(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;

	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			continue;
		}

		MakeMove(stateIndex,newMove); //generate a child
		 ImmediateGenerated++;

		 ConvertStateToDual(stateIndex);
		 newh=GetHuristicRegular(DualState); //calculate child h
		 if(newh+newg<=lookahead && newh==0 && IsGoal(stateIndex))
		 {
			 if(newg<UpperLimit) UpperLimit=newg;
			 printf("%s %d\n","Found Goal==>>",UpperLimit);
;
			 MakeMove(stateIndex,newMove);
			 continue;
		 }
		 

		 if( newg+newh<=lookahead && newg+newh<UpperLimit) // if the child cost is lower than the current goal - perform DFS
		 {

			 //rh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);
			 newh=HBLookahead3(stateIndex,newg,newh,lookahead,newMove);

		 }
			 h=MAX(h,newh-1);

			 MakeMove(stateIndex,newMove);

			 if(newh+newg<minf && newh+newg>lookahead)
			 {
				
				 minf=newh+newg;
			 }
			 if(g+h>lookahead)
			 {
				 
				 return h;
			 }
 	 
		 		 
	}//end for

return h;
}//End BLookahead

int HBLookahead1(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int opindex;
	int newblank;
	int newg;
	int newh;
	int rh;
	int maxH;
	int f=g+h;


	rh=0;
	maxH=0;
	

	if(f>lookahead)
	{		
		if(f<minf)
			minf=f;
		return -1;
	}
	if ((h==0) && (IsGoal(stateIndex)))
	{
		if (g<UpperLimit) UpperLimit=g;

		return 0;
	}


	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove); //generate a child


		 ImmediateGenerated++;

		 ConvertStateToDual(stateIndex);
		 newh=GetHuristicRegular(DualState); //calculate child h

		 rh=HBLookahead1(stateIndex,newg,newh,lookahead,newMove);


		 MakeMove(stateIndex,newMove);
		 if(rh==0) return 0; // If found goal - return

	}//end for
	return -1;
}//End BLookahead

int IIIExpandNode(int stateIndex,int g,int h,int lookahead, int PrevMove)
{
	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;



	for(int newMove=1;newMove<SIZE;newMove++)
	{
		if(newMove==PrevMove) continue; //if the suggested move is the same as the prevMove - ignore

		MakeMove(stateIndex,newMove);


		newg=g+1;

        ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		if( IsGoal(stateIndex))
		{

			if(newg<UpperLimit) UpperLimit=newg;
		}

		newh=MAX(h-1,newh);

		 newf=newh+newg;

		 if(newf<UpperLimit)
		 {
			 	hashval=CalcHash(old[stateIndex].boardState);
				newindex=SearchHash(old[stateIndex].boardState,hashval);
				if(newindex==stateIndex) newindex=-1;

				if(newf<=NextBestF) //need to add to CLOSE
				//if(newf<=0)
				{
					int IEstate=-1;
					bool IEflag=false;
					if(newindex==-1)//If this is a new node - add to CLOSE
					{
						Add2Close(stateIndex,hashval,newMove,newg,newh);
						IEstate=stateIndex;
						IEflag=true;
						//perform the IIIExpand
					}
					else//the node is already in memory
					{
						if(old[newindex].heaplink==-1)//if the node is in CLOSE
						{
							if(old[newindex].g>newg)
							{
								old[newindex].h=newh;
								old[newindex].g=newg;
								//IEstate=newindex;
								IEstate=stateIndex;
								IEflag=true;
								//perform the IIIExpand
							}
						}
						else //the node is in OPEN
						{
							if(old[newindex].g>newg)
							{
								//Need to delete it from the OPEN
								DeleteFromOpenList(newindex);

								old[newindex].h=newh;
								old[newindex].g=newg;
								old[newindex].PrevMove=newMove;
								IEstate=stateIndex;
								IEflag=true;
							}//end if
							
						}//end else node in OPEN
					}//end else node in memory
				
					//Immediate Generate nodes based on flags
					if(IEflag==true)
					{

						IE++;
						IIIExpandNode(IEstate,newg,newh,lookahead,newMove);
					}

				}//end if node cost is equal/lower than the current best node in OPEN
				else//need to add to OPEN
				{

					if(newindex==-1) //if this is a new node - add to OPEN
					{
						InsertHash(stateIndex,hashval,newMove,newg,newh);
					}
					else //this node is already in memory
					{
							if(old[newindex].heaplink==-1)//if this node is in the CLOSE - need to delete from CLOSE and add to OPEN
							{

							//	//Need to delete it from CLOSE and add it to OPEN
								if(old[newindex].g>newg)
								{
									reclosed++;
								FoundInC++;
								old[newindex].g=-1;
								old[newindex].h=-1;
								old[newindex].PrevMove=-1;
								for(int i=0;i<SIZE;i++)
								{
									old[newindex].boardState[i]=-2;
								}
								InsertHash(stateIndex,hashval,newMove,newg,newh);
								}


							}
							else //if this node is in the OPEN - need re-open
							{
								if(old[newindex].g>newg)//if we have a shorter path
								{
									reopened++;
								FoundInO++;
								if(old[newindex].h!=newh) old[newindex].h=newh;
								ReOpen(newindex,newg,newMove);
								}
							}
					}
				}
		 }


		MakeMove(stateIndex,newMove);
		
	}//end for

return -1;
}
void IClassicAStar (short s[SIZE], int lookahead)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclosed=0;
	FoundInC=0;
	FoundInO=0;
//	reclosed=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	NextBestF=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;




	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = -1;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;

	//Use IDA* with Lookahead as limit for the first node 

	
	 //if (lookahead>0) LimitedLookAhead(0,old[heap[0]].g,old[heap[0]].h,old[heap[0]].g+old[heap[0]].h+lookahead,old[heap[0]].PrevMove);
	
	//Searching loop:
	while((CurrentDepth!=100) && stored <FULL_OPEN && old[heap[0]].h+old[heap[0]].g<UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	{

		//Search for the next best f in the OPEN list priotiy queue
		bestf=old[heap[0]].h+old[heap[0]].g;
		if(bestf<UpperLimit)

		CurrentOpenNode=heap[0];
		//If the current node is a goal - stop the loop
		if (old[CurrentOpenNode].h==0 && old[CurrentOpenNode].g>UpperLimit)
		{
			CurrentDepth=100;
			goalDepth=old[CurrentOpenNode].g;
		}
		//Else (meaning, this is a node which is not a goal and with f value lower than upper limit - need to develop it
		else
		{
			DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			NextBestF=old[CurrentOpenNode].g+old[CurrentOpenNode].h;
			CurrentDepth=IIIExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,0,old[CurrentOpenNode].PrevMove);
			expanded++;			
		}
	}
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	PrintResult("IA*");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);

}

//------------------- Lookahead A-Star ---------------------
int FExpandNode1(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;
	int cindex;
	int IEstate=-1;
	bool IEflag=false;
	int IEg=0;
	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		if(g<UpperLimit) UpperLimit=g;
		return 100;
	}
	newg=g+1;
	for(int newMove=1;newMove<SIZE;newMove++)
	{
		if(newMove==PrevMove) continue;

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
			if(newg<UpperLimit) 
				UpperLimit=newg;

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		newh=MAX(h-1,newh);

		if(newh+newg<UpperLimit)
		{
		if(newg+newh<=NextBestF) //need to add to CLOSE
		{
			IEstate=-1;
			IEflag=false;
			IEg=newg;
			if(newindex==-1)//If this is a new node - add to CLOSE
			{
				cindex=FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
				IEstate=stateIndex;
				IEflag=true;
				//perform the IIIExpand
			}
			else//the node is already in memory
			{
				if(old[newindex].heaplink==-1)//if the node is in CLOSE
				{
					if(old[newindex].g>newg)
					{
						old[newindex].h=newh;
						//if (old[newindex].g<newg) IEg=old[stateIndex].g;
						old[newindex].cost=old[stateIndex].cost;
						IEstate=stateIndex;//newindex
						IEflag=true;
						//perform the IIIExpand
					}
				}
				else //the node is in OPEN
				{
					if(old[newindex].g>newg)
					{
						//Need to delete it from the OPEN
						DeleteFromOpenList(newindex);
						for(int i=0;i<SIZE;i++)
							old[newindex].boardState[i]=-1;
						old[newindex].g=-1;
						old[newindex].h=-1;
						old[newindex].cost=-1;
						IEstate=stateIndex;
						FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
						IEflag=true;
					}//end if
					
				}//end else node in OPEN
			}//end else node in memory
		
			//Immediate Generate nodes based on flags
			if(IEflag==true)
			{
				IE++;
				FExpandNode1(IEstate,newg,newh,newMove,lookahead);
			}
			
		}
		else
		{
		
			int ActualLH;
			if(bestc<=lookahead) ActualLH=MIN(NextBestC,lookahead);
			else
				ActualLH=-1;
		if(newg+newh<=ActualLH )
		{
			minf=10000;
			int tempLH=newg+newh;
			while(tempLH<=ActualLH && tempLH<UpperLimit)
			{
				//FIDAStar(stateIndex,newg,newh,tempLH,newMove);
				HBLookahead1(stateIndex,newg,newh,tempLH,newMove);
				tempLH=minf;
				//printf("%s %d %s %d\n","tempLH=",tempLH,"ActualLH=",ActualLH);
				minf=100000;
			}
			newcost=tempLH;
		}
		else
		{
			newcost=newg+newh;
		}
		if(CostArr[newcost]==-1) CostArr[newcost]=1;
		// if the child is unique - add it to the OPEN list
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
				FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
						reopened++;
					FoundInC++;
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
						reopened++;
						FoundInO++;

						if(old[newindex].h!=newh) old[newindex].h=newh;
						if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
						FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		}
		}
		MakeMove(stateIndex,newMove);
	}
	return -1;
}


int FExpandNode2(int stateIndex, int g, int h, int PrevMove,int lookahead)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


	//printf("%s\n","---------------- Expand -------------");
	//printf("%s %d %s %d %s %d %s %d\n","cost=",old[stateIndex].cost,"lookahead=",lookahead,"g=",g,"h=",h);
	//string mystr11;
	//getline (cin,mystr11);
	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(g<UpperLimit) UpperLimit=g;
		printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	newg=g+1;
	for(int newMove=1;newMove<SIZE;newMove++)
	{
		if(newMove==PrevMove) continue;

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(newg<UpperLimit) UpperLimit=newg;
			printf("%s %d\n","found goal-->>",newg);
		}

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		//printf("%s %d\n","newh=",newh);
		//string mystr1;
		//getline (cin,mystr1);
		newh=MAX(h-1,newh);
		//printf("%s %d %s %d\n","newh=",newh,"bestc=",bestc);

		if(newh+newg<UpperLimit)
		{
		if(newg+newh<=bestf)
		//if(newg+newh<bestc) //need to add to CLOSE
		{
			//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","IE - parentg=",g,"parenth=",h,"childg=",newg,"childh=",newh,"lookahead=",lookahead,"bestc=",bestc);
			//string mystr;
			//getline (cin,mystr);
			int IEstate=-1;
			bool IEflag=false;
			int IEg=newg;
			if(newindex==-1)//If this is a new node - add to CLOSE
			{
				//newcost=FIDAStar(stateIndex,newg,newh,lookahead,newMove);
				int cindex=FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
				//IEstate=cindex;
				IEstate=stateIndex;
				IEflag=true;
				//perform the IIIExpand
			}
			else//the node is already in memory
			{
				if(old[newindex].heaplink==-1)//if the node is in CLOSE
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d %s %d %s %d\n","in close - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"index=",newindex,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost,"index=",stateIndex);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						old[newindex].h=newh;
						//if (old[newindex].g<newg) IEg=old[stateIndex].g;
						old[newindex].cost=old[stateIndex].cost;
						IEstate=stateIndex;//newindex
						IEflag=true;
						//perform the IIIExpand
					}
				}
				else //the node is in OPEN
				{
					//printf("%s %d %s %d %s %d %s %d %s %d %s %d\n","in open - g=",old[newindex].g,"h=",old[newindex].h,"cost=",old[newindex].cost,"new - g=",newg,"h=",newh,"cost=",old[stateIndex].cost);
					//string mystr1;
					//getline (cin,mystr1);
					if(old[newindex].g>newg)
					{
						//Need to delete it from the OPEN
						FDeleteFromOpenList(newindex);
						for(int i=0;i<SIZE;i++)
							old[newindex].boardState[i]=-1;
						old[newindex].g=-1;
						old[newindex].h=-1;
						old[newindex].cost=-1;
						IEstate=stateIndex;
						FAdd2Close(stateIndex,hash,newMove,newg,newh,bestc);
						//old[newindex].h=newh;
						//old[newindex].g=newg;
						//old[newindex].PrevMove=newMove;
						//if(old[newindex].cost>newg+newh) old[newindex].cost=old[stateIndex].cost;
						//IEstate=newindex;
						IEflag=true;
					}//end if
					
				}//end else node in OPEN
			}//end else node in memory
		
			//Immediate Generate nodes based on flags
			if(IEflag==true)
			{
				//printf("%s\n","IE");
				//printf("%s","before:");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");

				IE++;
				FExpandNode2(IEstate,newg,newh,newMove,lookahead);
				//printf("%s","after :");
				//for (int i=0;i<SIZE;i++)
				//	printf("%d ",old[IEstate].boardState[i]);
				//printf("%s\n","");
			}
			
		}
		else
		{
		if(newg+newh<bestc) newcost=bestc;
			else newcost=newg+newh;
		
		if(newindex==-1)
		{
			if(newcost<UpperLimit)
			{
			//printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parentf=",g+h);
			FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newcost<UpperLimit)
					{
						reopened++;
					FoundInC++;
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					FInsertHash(stateIndex,hash,newMove,newg,newh,newcost);
					}
				}
				else
				{
					if(newcost<UpperLimit)
					{
						reopened++;
					FoundInO++;
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);

					if(old[newindex].h!=newh) old[newindex].h=newh;
					if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					FReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		}
		}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}


void LHAStar2(short s[SIZE], int lookahead)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		old[i].h=-1;
		old[i].cost=1000;
		for(int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
		bucket[i] = MAX_HASH;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}

	for(int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;
//	sameV=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
//	reclosed=0
	FoundInC=0;
	FoundInO=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	NextBestF=0;
	NextBestC=0;




	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = -1;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	int f = old[empty].g + old[empty].h; 
	minf=10000;
    old[empty].cost=f;
	empty++;
	heap[0]=0;
	//

	//Use IDA* with Lookahead as limit for the first node 

	bestc=0;

	//Searching loop:
	//While the goal was not found and hash table is not full and the current f value is lower than the upper limit
	while((CurrentDepth!=100) && stored <FULL_OPEN && old[heap[0]].cost<UpperLimit && OpenStart>=0)//bestf+lookahead<UpperLimit)
	{
		//Search for the next best f in the OPEN list priotiy queue
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		NextBestC=bestc+1;
		while(OpenStart>1 && CostArr[NextBestC]==-1)
			NextBestC++;

		innerclock=(double)clock();
		CurrentOpenNode=heap[0];
	
		//Else (meaning, this is a node which is not a goal and with f value lower than upper limit - need to develop it
		NextBestF=old[heap[0]].h+old[heap[0]].g;	
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			
		CurrentDepth=FExpandNode1(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,old[CurrentOpenNode].h+old[CurrentOpenNode].g+lookahead);
		
		expanded++;	
	}
	//printf("%s %d %s %d %s %d %s %d\n","h=",old[heap[0]].h," g=",old[heap[0]].g," cost=",old[heap[0]].cost,"lookahead=",lookahead);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	PrintResult("AL*(%d)",lookahead);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
//	printf("%s","sameV = ");
//	printf("%d \n",sameV);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);

}




int CExpandNode1(int stateIndex, int g, int h, int PrevMove)
{
	int hash;
	int newindex;
	int newh;
	int newg;
	int newcost;
	FILE *solution;
	int LHResult;


//	printf("%s\n","---------------- Expand -------------");
	LHResult=-1;
	newcost=1000;
	if(IsGoal(stateIndex))
	{
		printf("%s\n","found goal");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(old[stateIndex].g<UpperLimit) UpperLimit=old[stateIndex].g;
		//printf("%s %d\n","found goal-->>",UpperLimit);
		//goalDepth=old[stateIndex].g;
		return 100;

	}
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if(newMove==PrevMove) continue;

		//else - generate the potential child by modifying the child
		MakeMove(stateIndex,newMove);
		//if(IsGoal(stateIndex))
		//{
		////printf("%s\n","found goal");
		////for(int i=0;i<SIZE;i++)
		////	printf("%d ",old[stateIndex].boardState[i]);
		////printf("%s\n","");
		//	if(newg<UpperLimit) UpperLimit=newg;
		////printf("%s %d\n","found goal-->>",UpperLimit);
		////goalDepth=old[stateIndex].g;

		//}

		hash=CalcHash(old[stateIndex].boardState);
		newindex=SearchHash(old[stateIndex].boardState,hash);
		if(newindex==stateIndex) newindex=-1;
		newcost=1000;
		newg=g+1;
        ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		//newh=GetHuristicRegular(stateIndex,0);
		newh=MAX(h-1,newh);
		int newf=newh+newg;
		
		if(newindex==-1)
		{
			if(newf<UpperLimit)
			{
			//printf("%s %d %s %d %s %d %s %d\n","Adding - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parentf=",g+h);
			InsertHash(stateIndex,hash,newMove,newg,newh);	
			}
		}
		else
		{
			if(newg<old[newindex].g)
			{
				if(old[newindex].heaplink==-1)
				{
					if(newf<UpperLimit)
					{
					old[newindex].g=-1;
					old[newindex].h=-1;
					old[newindex].cost=0;
					for (int i=0;i<SIZE;i++)
						old[newindex].boardState[i]=-1;
					reclosed++;
					FoundInC++;
					//printf("%s %d %s %d %s %d %s %d\n","Reclose - cost=",newcost," f=",newg+newh,"lookahead=",lookahead,"parenth=",g+h);
					InsertHash(stateIndex,hash,newMove,newg,newh);
					}
				}
				else
				{
					if(newf<UpperLimit)
					{
					//	printf("%s\n","~~~~~~~~~~~~~~~~~~~ ReOpening ~~~~~~~~~~~~~~~~~");
						//string mystr1;
						//getline (cin,mystr1);
					reopened++;
					FoundInO++;
					if(old[newindex].h!=newh) old[newindex].h=newh;
					//if(old[newindex].cost!=newcost) old[newindex].cost=newcost;
					ReOpen(newindex,newg,newMove);
					}
				}
			}
		}
		//}
		//}
		MakeMove(stateIndex,newMove);
	}
	//string mystr1;
	//getline (cin,mystr1);
	return -1;
}



void ClassicAStar (short s[SIZE],char* algorithmName)
{
	//Variables
	int blank;
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	double innerclock;
	double time2loop;
	FILE *solution;


	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	reclosed=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	FoundInC=0;
	FoundInO=0;

	//Find the blank position
	for (blank=0;blank<SIZE;blank++)
		if (s[blank]==0) break;

	//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = -1;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	//old[empty].h=bestf=GetHuristicRegular(0,0);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;
	//
	
	//Searching loop:
	//While the goal was not found and hash table is not full and the current f value is lower than the upper limit
	while(CurrentDepth!=100 && stored <FULL_OPEN && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		CurrentDepth=CExpandNode1(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		expanded++;
	}

	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;

	if(IsGoal(heap[0])) goalDepth=old[heap[0]].g;

	goalDepth=UpperLimit;
	PrintResult(algorithmName);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
	//string mystr;
	//getline (cin,mystr);


}
//-----------------BPMX--------------------

int BExpandNode(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int blank;
	int newblank;
	int newindex;
	int opindex;

	int newg;
	int newh;
	int newf;
	int tile;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	if(IsGoal(stateIndex))
	{
		goalDepth=old[stateIndex].g;
		return 100;
	}

	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		maxH=MAX(maxH,newh-2);

		newf=newh+newg;
	    //Add the child to the children list
		for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		children[ChildNum].add2Open=false;
		children[ChildNum].g=newg;
		children[ChildNum].h=newh;
		children[ChildNum].PrevMove=newMove;
		generated++;
		ChildNum++;
		MakeMove(stateIndex,newMove);
	}

	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		children[i].h=MAX(maxH,children[i].h); // BPMX!
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
				}
				else
				{
				reopened++;
				FoundInC++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				boo=false;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					ReOpen(newindex,children[i].g,children[i].PrevMove);
				}
			}
		}//end if (for existing child)
		else
			boo=true;
		if (boo) 
		{
			children[i].add2Open=true;
		}
		else
		{
			children[i].add2Open=false;
		}
	}//end for

	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			hashval=CalcHash(children[i].boardState);
			InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

/**
 Expand node of IBPMX
 **/
int IIBExpandNode(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;
		 int cost;/* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int newindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	FILE *solution;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)
			continue;

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
			if(UpperLimit>newg) UpperLimit=newg;

		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		
		maxH=MAX(maxH,newh-2); // BPMX

        newf=newh+newg;
		//Add the child to the children list
		for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		children[ChildNum].add2Open=false;
		children[ChildNum].g=newg;
		children[ChildNum].h=newh;
		children[ChildNum].PrevMove=newMove;
		children[ChildNum].cost=old[stateIndex].cost;
		generated++;
		ChildNum++;
		MakeMove(stateIndex,newMove); // Undo
	}

	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		if(maxH>children[i].h) 
			BUpdate++;
		children[i].h=MAX(maxH,children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				if(old[newindex].g<=children[i].g)
					boo=false;
				else
				{
					reopened++;
					FoundInC++;
					boo=true;
					for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				boo=false;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					if(old[newindex].cost!=children[i].cost) old[newindex].cost=MAX(children[i].cost,old[newindex].cost); 
					ReOpen(newindex,children[i].g,children[i].PrevMove);
				}
			}
		}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
			children[i].add2Open=true;
		else
			children[i].add2Open=false;
	}//end for

	//After updating the children heuristic, need to find new maxH

	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			if(children[i].cost<children[i].h+children[i].g)children[i].cost=children[i].h+children[i].g ;
			if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
			if(children[i].h+children[i].g<UpperLimit)
			{
				hashval=CalcHash(children[i].boardState);
				if((children[i].h+children[i].g<=NextBestF) && PerformTrivial )
				{
					IE++;
					int cindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);//,children[i].cost);
					IIBExpandNode(cindex,children[i].g,children[i].h,children[i].PrevMove);
				}
				else
				{
					
					InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);//,children[i].cost);
				}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

	return -1;

}

int HBLookahead(int stateIndex,int g, int h, int lookahead, int PrevMove)
{
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;
	maxH=0;
	//printf("%s %d %s %d\n","lookahead=",lookahead,"g=",g);

	if (IsGoal(stateIndex))
	{
		if (g<UpperLimit) UpperLimit=g;
		//printf("%s %d\n","goal depth is: ",UpperLimit);
		//printf("%s %d %s %d\n","ph1=",old[stateIndex].h," pg=",old[stateIndex].g);
		//return -1; //do we need it? I think we do otherwise it will continue on
		return g;
	}



	if (h+g>lookahead)
	{
		//printf("%s\n","f bigger than lookahead, returning h");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s %d %s %d %s %d\n","h=",h,"g=",g,"lookahead=",lookahead);
		//printf("%s\n","");
		if(g+h<minf) minf=g+h;
		return h;//return 1000; // the cost is higher than the lookahead level - need to rollback
	}
	//if (IsGoal(stateIndex))
	//{
	//	//for (int k=0;k<SIZE;k++)
	//		//printf("%d ",old[stateIndex].boardState[k]);
	//	if (g<UpperLimit) UpperLimit=g;
	//	printf("%s %d %s %d %s %d %s %d\n","goal depth is: ",UpperLimit,"parent f=",old[stateIndex].h+old[stateIndex].g," lookahead=",lookahead,"stateIndex=",stateIndex);
	//	return g;
	//}


	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		//if(IsGoal(stateIndex)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		 ConvertStateToDual(stateIndex);
		 newh=GetHuristicRegular(DualState); //calculate child h
		 
		 //printf("%s %d %s %d %s %d\n","newh=",newh,"newg=",newg,"oldh=",h);
		 //if(newh-h>1 || newh-h<-1) {printf("%s %d %s %d\n","----->>>>>found inconsistency! newh=",newh," h=",h);
		 	//string mystr;
			//getline (cin,mystr);

		 
		 if( newg+newh<UpperLimit) //&& newg+newh<=lookahead) // if the child cost is lower than the current goal - perform DFS
		 {
			 rh=HBLookahead(stateIndex,newg,newh,lookahead,newMove);
		 }

		 MakeMove(stateIndex,newMove);
		 h=MAX(h,rh-1);
		 
		 if(g+h>lookahead)
		 {
			 if(g+h<minf) minf=g+h;
			 return h;
		 }
		 	 
		 		 
	}//end for

return h;
}//End BLookahead

int HBLookahead(short state[SIZE],int g, int h, int lookahead, int PrevMove)
{
	printf("%s\n","in lookahead");
	int opindex;
	int newg;
	int newh;
	int rh;
	int maxH;



	rh=0;
	maxH=0;
	//printf("%s %d %s %d\n","lookahead=",lookahead,"g=",g);

	if (IsGoal(state))
	{
		if (g<UpperLimit) UpperLimit=g;
		printf("%s %d\n","goal depth is: ",UpperLimit);
		//printf("%s %d %s %d\n","ph1=",old[stateIndex].h," pg=",old[stateIndex].g);
		//return -1; //do we need it? I think we do otherwise it will continue on
		return g;
	}



	if (h+g>lookahead)
	{
		//printf("%s\n","f bigger than lookahead, returning h");
		//for(int i=0;i<SIZE;i++)
		//	printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s %d\n","h=",h);
		//printf("%s\n","");
		if(h+g<minf) minf=h+g;
		return h;//return 1000; // the cost is higher than the lookahead level - need to rollback
	}
	//if (IsGoal(stateIndex))
	//{
	//	//for (int k=0;k<SIZE;k++)
	//		//printf("%d ",old[stateIndex].boardState[k]);
	//	if (g<UpperLimit) UpperLimit=g;
	//	printf("%s %d %s %d %s %d %s %d\n","goal depth is: ",UpperLimit,"parent f=",old[stateIndex].h+old[stateIndex].g," lookahead=",lookahead,"stateIndex=",stateIndex);
	//	return g;
	//}


	//if the cost is lower than lookahead and the state is not goal - need to develope its children
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(state,newMove); //generate a child
		//printf("%s","Goining deeper: ");
		//for (int i=0;i<SIZE;i++)
		//	 printf("%d ",old[stateIndex].boardState[i]);
		//printf("%s\n","");
		if(IsGoal(state)) printf("%s %d\n","goal depht is-->>", newg);

		 ImmediateGenerated++;

		 printf("%s","Array is:");
		 for (int i=0;i<SIZE;i++)
			 printf("%d ",state[i]);
		 printf("%s\n","");
		 ConvertStateToDual(state);
		 newh=GetHuristicRegular(DualState); //calculate child h
		 //printf("%s %d %s %d\n","newh=",newh,"newg=",newg);
		 //if(newh-h>1 || newh-h<-1) {printf("%s %d %s %d\n","----->>>>>found inconsistency! newh=",newh," h=",h);
		 //	string mystr;
			//getline (cin,mystr);}

		 
		 if( newg+newh<UpperLimit ) // if the child cost is lower than the current goal - perform DFS
		 {
			 rh=HBLookahead(state,newg,newh,lookahead,newMove);
		 }

		 MakeMove(state,newMove);
		 //printf("%s %d\n","h before update:",h);
		 h=MAX(h,rh-1);
		 //printf("%s %d\n","h after update:",h);
		 if(g+h>lookahead)
		 {
			 if(g+h<minf) minf=g+h;
			 //printf("%s %d %s %d %s %d %s %d\n","h after update=",h," g=",g," newg=",newg, " lookahead=",lookahead);
			 return h;
		 }
		 	 
		 		 
	}//end for
printf("%s\n","out of lookahead");
return h;
}//End BLookahead

/**
 Expand node procedure for AL* with BPXM (op. 1)
 **/
int IIBExpandNodeLH(int stateIndex,int g,int h, int PrevMove,int lookahead)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 int cost;
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int newindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// Generate all the immediate children and compute maxH for BPXM(1):
	newg=g+1;
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)
			continue;

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
			printf("%s %d\n","Found Goal:::",UpperLimit);
			return 0;
		}
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		if(maxH>newh) 
			BUpdate++;
		newh=MAX(maxH,newh);
		minf=INFINITY;
		
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 if(newf<UpperLimit)
		 {
			 //Add the child to the children list
			 for(int i=0;i<SIZE;i++)
				children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
			 children[ChildNum].add2Open=false;
			 children[ChildNum].g=newg;
			 children[ChildNum].h=newh;
			 children[ChildNum].PrevMove=newMove;
			 children[ChildNum].cost=MAX(newf,old[stateIndex].cost);//newf;
			 
			 generated++;
			 ChildNum++;		
		 }
		 MakeMove(stateIndex,newMove); // Undo
	}

	//Now, update the children heuristic based on maxH found (this is BPMX(1) before the lookahead)
	for (int i=0;i<ChildNum;i++)
		children[i].h=MAX(maxH,children[i].h); 

	// Call lookahead from every node
	int maxLH=0;
	int tempH=0;
	int tempLH;
	for (int i=0;i<ChildNum;i++)
	{
		children[i].h=MAX(maxLH,children[i].h); // BPMX during the lookahead
		tempLH = children[i].h+children[i].g;
		if(tempLH<=lookahead /*&& children[i].cost>=old[stateIndex].cost*/ && tempLH<UpperLimit)
		{
			LHnodes++;
			minf=INFINITY;
			tempH=0;
			while(tempLH<=lookahead && tempLH<UpperLimit)
			{
				minf=INFINITY;
				tempH=HBLookahead3(children[i].boardState,children[i].g,children[i].h,tempLH,children[i].PrevMove);
				tempLH=MAX(tempH+children[i].g,tempLH+1);
			}
			children[i].h=MAX(children[i].h,tempH);
			children[i].cost=MAX(minf,children[i].cost);
			maxLH=MAX(maxLH,children[i].h-2);
		}
		
	}

	bool boo=true;
	for (int i=0;i<ChildNum;i++)
	{
		children[i].h=MAX(children[i].h,maxLH); // BPMX(1) after the Lookahead
		if(children[i].cost<children[i].h+children[i].g) children[i].cost=children[i].h+children[i].g;

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;

		boo=true;
		// if the state already exists
		if(newindex!=-1)
		{		
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				if(old[newindex].g<=children[i].g)
				{
					boo=false;
				}
				else
				{
					reopened++;
					FoundInC++;
					boo=true;
					for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				boo=false;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					if(old[newindex].cost!=children[i].cost) old[newindex].cost=MAX(children[i].cost,old[newindex].cost);
					FReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
		}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}
	}//end for

	
	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			children[i].h=MAX(maxLH,children[i].h);
			if(children[i].g+children[i].h>children[i].cost) children[i].cost= children[i].g+children[i].h;
			if(children[i].cost<UpperLimit)
			{
				hashval=CalcHash(children[i].boardState);
				if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
				FInsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}
int IIBExpandNodeLH2(int stateIndex,int g,int h, int PrevMove,int lookahead)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 //int boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 int cost;
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int newindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;

	//maxH=0;
	maxH=h-1;
	ChildNum=0;

	// Generate all the immediate children:
	newg=g+1;
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		//newblank=opindex;
		MakeMove(stateIndex,newMove);
		if(IsGoal(stateIndex))
		{
			if(UpperLimit>newg) UpperLimit=newg;
			printf("%s %d\n","Found Goal:::",UpperLimit);
			return 0;
		}

		ConvertStateToDual(stateIndex);
		
		newh=GetHuristicRegular(DualState);
		//printf("%s %d %s %d\n","bnewh :",newh,"maxH=",maxH);
		if(maxH>newh) BUpdate++;
		int flag=0;
		//if(newh+newg>old[stateIndex].cost) flag=1;
		newh=MAX(maxH,newh);
		minf=INFINITY;
		//printf("%s\n","beforeLH");
		//printf("%s %d %s %d %s %d %s %d\n","newh before change:",newh,"newg=",newg,"NextbestF=",NextBestF,"lookahead=",lookahead);
		if(newh+newg<=lookahead /*&& newg+newh>=old[stateIndex].cost &&*/&& newh+newg<UpperLimit)
		{
			LHnodes++;
	
			int tempLH=newh+newg;
			//int tempLH=lookahead;
			int tempH=0;
			while(tempLH<=lookahead && tempLH<UpperLimit)
			{
				
				minf=INFINITY;
				tempH=HBLookahead3(stateIndex,newg,newh,tempLH,newMove);
				//printf("%s %d %s %d\n","minf=",minf,"lookahead=",lookahead);
				tempLH=minf;
			}
			if(tempH>newh) LHUpdate++;
			newh=MAX(newh,tempH);
		}
		else
			minf=MAX(newg+newh,old[stateIndex].cost);

		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 if(newf<UpperLimit)
		 {
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].add2Open=false;
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 children[ChildNum].cost=minf;//newh+newg;
	//	 printf("%s %d %s %d\n","childf=",children[ChildNum].g+children[ChildNum].h,"childc=",children[ChildNum].cost);
		    //string mystr;
	//getline (cin,mystr);
		 //if(CostArr[children[ChildNum].cost]==-1) CostArr[children[ChildNum].cost]=1;
		 generated++;
		 ChildNum++;
		
		 }
		 MakeMove(stateIndex,newMove);
	}

	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		if(maxH>children[i].h) BLHUpdate++;
		children[i].h=MAX(maxH,children[i].h);
		if(children[i].cost<children[i].h+children[i].g) children[i].cost=children[i].h+children[i].g;
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//	children[i].h=old[stateIndex].h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		bool boo=true;
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				if(old[newindex].g<=children[i].g)
				{
					boo=false;

				}
				else
				{
					reopened++;
					FoundInC++;
						boo=true;
						for (int j=0;j<SIZE;j++)
						old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
					old[newindex].cost=10000;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				boo=false;
				//FoundInO++;
				if(old[newindex].g>children[i].g)
				{
					reopened++;
					FoundInO++;
					//old[newindex].g=children[i].g;
					boo=false;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					if(old[newindex].cost!=children[i].cost) old[newindex].cost=MAX(children[i].cost,old[newindex].cost);
					FReOpen(newindex,children[i].g,children[i].PrevMove);
				}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
			}
}//end if (for existing child)
		else
			boo=true;
		//boo=true; //for testing
		if (boo) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		else
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for
	

	//printf("%s\n","-- before insert to open --");
	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			//children[i].h=MAX(maxLH,children[i].h);
			if(children[i].g+children[i].h>children[i].cost) children[i].cost= children[i].g+children[i].h;
			if(children[i].cost<UpperLimit)
			{
			//printf("%s %d\n","childh before change:",children[i].h);
			//children[i].h=MAX(maxH,children[i].h);
			//printf("%s %d\n","childh after change:",children[i].h);
				hashval=CalcHash(children[i].boardState);
				if(children[i].h+children[i].g<=NextBestF)
				{
					IE++;
					int cindex=FAdd2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
					 if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
				//	//printf("%s %d %s %d\n","Perform IE-->NextBestF=",NextBestF,"f=",children[i].g+children[i].h);
					int r=IIBExpandNodeLH2(cindex,children[i].g,children[i].h,children[i].PrevMove,lookahead);
				//	//if (r==0) return 0;
				}
				else
				{
					//printf("%s %d %s %d\n","Adding, f=",children[i].g+children[i].h,"cost=",children[i].cost);
					 if(CostArr[children[i].cost]==-1) CostArr[children[i].cost]=1;
					FInsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h,children[i].cost);
				}
			}

		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void BPMXAStar(short s[SIZE])
{
		//Variables
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;
	FILE *solution;

	//srand ( (unsigned)time ( NULL ) );

	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;
	CurrentDepth=0;

	while ( CurrentDepth!=100 && stored <FULL_OPEN && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list		
		CurrentDepth=BExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		expanded++;
	}
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	PrintResult("A* with BPMX");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf ("%s","Duplicated = ");
	printf ("%d \n",duplicatCounter);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);
}

int IBPMXExpand(int stateIndex,int g,int h, int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int newindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;
	string mystr;


	maxH=h-1;
	ChildNum=0;


	//printf("%s\n","generating children");
	newg=g+1;
	// Generate all the immediate children:
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove);
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		//printf("%s %d\n","child h=",newh);
		//getline (cin,mystr);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 if (IsGoal(children[ChildNum].boardState))	
		 {
			 if(UpperLimit>children[ChildNum].g)
				 UpperLimit=children[ChildNum].g;
			 printf("%s %d\n","goal depth=", UpperLimit);
		 }
		 generated++;
		 ChildNum++;
		 
		 MakeMove(stateIndex,newMove);
		 
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	
	


	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		///printf("%s %d\n","child h after change1:",children[i].h);
		//if(children[i].g+children[i].h<old[stateIndex].g+old[stateIndex].h)
		//if(children[i].g+children[i].h<g+h)
			//children[i].h=old[stateIndex].h-1;
			//children[i].h=h-1;
		//printf("%s %d\n","child h after change2:",children[i].h);

		//Search for the child in memory
		hashval=CalcHash(children[i].boardState);
		newindex=SearchHash(children[i].boardState,hashval);
		if(newindex==stateIndex) newindex=-1;
		//printf("%s %d\n","newindex=",newindex);

		//if(newindex!=-1 && old[newindex].PrevMove!=children[i].PrevMove)
		//{
		//	printf("%s\n","different prev moves");
		//string mystr;
		//getline (cin,mystr);
		//}
		//printf("%s %d\n","newindex=",newindex);

		
		short boo=0; //0 - add new; 1 - don't add old; 2 - reopen (already appear in open)
		// if the state already exists
		if(newindex!=-1)
		{
			
			//Check if exists in close list
			if(old[newindex].heaplink==-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				FoundInC++;
				//if(old[newindex].h>children[i].h)
				//{
				//	children[i].h=old[newindex].h;
				//	UpdateH=true;
				//}
				if(old[newindex].g<=children[i].g)
				{
					boo=1;
					//if(old[newindex].h>=children[i].h)
					//boo=false;

				}
				//else
				//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
				//		boo=false;
				//if(boo) //(g in close is lower than g in children)
				else
				{
						boo=0;
						//for (int j=0;j<SIZE;j++)
						//old[newindex].boardState[j]=-1;
					old[newindex].h=-1;
					old[newindex].g=-1;
				}
				
			}// end if - if in close list
		
			//else //the node is in the open list
			if(old[newindex].heaplink!=-1)
			{
				//printf("%s","Found the state in close ");
				//for(int j=0;j<SIZE;j++)
				//	printf("%d ",old[newindex].boardState[j]);
				//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
				//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
				//string mystr;
				//getline (cin,mystr);
				boo=1;
				FoundInO++;

				//if(old[newindex].h>children[i].h)
				//	children[i].h=old[newindex].h;
				if(old[newindex].g>children[i].g)
				{
					//old[newindex].g=children[i].g;
					boo=2;
					if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
					maxH=MAX(maxH,old[newindex].h-2);
					//ReOpen(newindex,children[i].g,children[i].PrevMove);
				}			
			}
		}//end if (for existing child)
		else
			boo=0;
		//boo=true; //for testing
		if (boo==0) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		if(boo==1)
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}
		if(boo==2)
		{
			ReOpen(newindex,children[i].g,children[i].PrevMove);
			children[i].add2Open=false;
		}

		
	//string mystr;
	//getline (cin,mystr);
	}//end for

	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			hashval=CalcHash(children[i].boardState);
			if(children[i].h+children[i].g<UpperLimit)
			{
			//if(children[i].h+children[i].g>old[heap[0]].g+old[heap[0]].h)
			if(children[i].h+children[i].g>NextBestF) 
			{			
				InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
			}
			else
			{
				InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
			}

			}
		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void IBPMXAStar(short s[SIZE],char* algorithmName)
{
		//Variables
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;

	//srand ( (unsigned)time ( NULL ) );

	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	BUpdate=0;
	BLHUpdate=0;
	

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
	NextBestF=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	empty++;
	heap[0]=0;

	while (CurrentDepth!=100 && old[heap[0]].h+old[heap[0]].g<UpperLimit && stored <FULL_OPEN && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		CurrentOpenNode=heap[0];
		if(IsGoal(CurrentOpenNode))
		{
			goalDepth=old[CurrentOpenNode].g;
			break;
		}
		DeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
			
		NextBestF=old[CurrentOpenNode].h+old[CurrentOpenNode].g;
		//CurrentDepth=IBPMXExpand(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		CurrentDepth=IIBExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		//CurrentDepth=BExpandNode(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove);
		expanded++;
	}
	//printf("%s %d %s %d\n","old[heap[0]].h=",old[heap[0]].h," old[heap[0]].g=",old[heap[0]].g);
goalDepth=UpperLimit;
endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
//	PrintResult2File("AStartLH",lookahead);
	PrintResult(algorithmName);
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf("%s %d %s %d \n","BUpdate=",BUpdate,"BLHUpdate=",BLHUpdate);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}





int ILHBPMXExpand(int stateIndex,int g,int h, int lookahead,int PrevMove)
{
	 struct child
	 {                           
		 short boardState[SIZE];
		 short g;                                      /* distance from initial state */
		 short h;                        /* static heuristic distance from goal state */
		 short PrevMove;                                /* previous position of blank */
		 bool add2Open;
	 } children[SIZE];

	int newindex;

	int newg;
	int newh;
	int newf;
	int flag=-1;

	int hashval;
	int maxH;  //holds the maximum H between all immediate children
	int ChildNum;
	string mystr;


	//int LHResult=HBLookahead(stateIndex,g,h,lookahead,PrevMove);
	maxH=h-1;
	ChildNum=0;


	//printf("%s\n","generating children");
	newg=g+1;
	// Generate all the immediate children:
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (PrevMove==newMove)// 0 -> 4 -> 8
		 {
			 //printf("%s %d\n","not allowed move: ",opindex);
			continue;
		}

		MakeMove(stateIndex,newMove);
		//printf("%s","the child node is:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
		ConvertStateToDual(stateIndex);
		newh=GetHuristicRegular(DualState);
		//printf("%s %d\n","child h=",newh);
		//getline (cin,mystr);
		maxH=MAX(maxH,newh-2);

		 newf=newh+newg;
		 //Add the child to the children list
		 for(int i=0;i<SIZE;i++)
			children[ChildNum].boardState[i]=old[stateIndex].boardState[i];
		 children[ChildNum].g=newg;
		 children[ChildNum].h=newh;
		 children[ChildNum].PrevMove=newMove;
		 if (IsGoal(children[ChildNum].boardState))	
		 {
			 if(UpperLimit>children[ChildNum].g)
				 UpperLimit=children[ChildNum].g;
			// printf("%s %d %s %d %s %d %s %d\n","goal depth=", UpperLimit,"ph=",h,"pg=",g,"lookahead=",lookahead);
		 }
		 children[ChildNum].add2Open=false;
		 generated++;
		 ChildNum++;
		 
		 MakeMove(stateIndex,newMove);
		 
		// printf("%s","state after undo:");
		//for (int l=0;l<SIZE;l++)
		//	printf("%d ",old[stateIndex].boardState[l]);
		//printf("%s\n","");
	}
	
	


	//printf("%s %d\n","maxh=",maxH);
	//Now, update the children heuristic based on maxH found:
	for (int i=0;i<ChildNum;i++)
	{
		//printf("%s %d\n","child h before change:",children[i].h);
		children[i].h=MAX(maxH,children[i].h);
		if(children[i].h+children[i].g<UpperLimit)
		{
			//if(children[i].h+children[i].g>=UpperLimit) printf("%s\n","extra");
			///printf("%s %d\n","child h after change1:",children[i].h);

			//Search for the child in memory
			hashval=CalcHash(children[i].boardState);
			newindex=SearchHash(children[i].boardState,hashval);
			if(newindex==stateIndex) newindex=-1;
			//printf("%s %d\n","newindex=",newindex);

		
			short boo=0; //0 - add new; 1 - don't add old; 2 - reopen (already appear in open)
			// if the state already exists
			if(newindex!=-1)
			{
			
				//Check if exists in close list
				if(old[newindex].heaplink==-1)
				{
					//printf("%s","Found the state in close ");
					//for(int j=0;j<SIZE;j++)
					//	printf("%d ",old[newindex].boardState[j]);
					//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
					//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
					//string mystr;
					//getline (cin,mystr);
					FoundInC++;
					//if(old[newindex].h>children[i].h)
					//{
					//	children[i].h=old[newindex].h;
					//	UpdateH=true;
					//}
					if(old[newindex].g<=children[i].g)
					{
						boo=1;
						//if(old[newindex].h>=children[i].h)
						//boo=false;

					}
					//else
					//if(old[newindex].g==children[i].g && old[newindex].h>=children[i].h)
					//		boo=false;
					//if(boo) //(g in close is lower than g in children)
					else
					{
							boo=0;
						for (int j=0;j<SIZE;j++)
							old[newindex].boardState[j]=-1;
						old[newindex].h=-1;
						old[newindex].g=-1;
					}
					
				}// end if - if in close list
		
				//else //the node is in the open list
				if(old[newindex].heaplink!=-1)
				{
					//printf("%s","Found the state in close ");
					//for(int j=0;j<SIZE;j++)
					//	printf("%d ",old[newindex].boardState[j]);
					//printf("%s %d %s %d\n","h=",old[newindex].h," g=",old[newindex].g);
					//printf("%s %d %s %d\n","childh=",children[i].h," chilg=",children[i].g);
					//string mystr;
					//getline (cin,mystr);
					boo=1;
					FoundInO++;

					//if(old[newindex].h>children[i].h)
					//	children[i].h=old[newindex].h;
					if(old[newindex].g>children[i].g)
					{
						//old[newindex].g=children[i].g;
						boo=2;
						if(old[newindex].h<children[i].h)
						old[newindex].h=children[i].h;
						maxH=MAX(maxH,old[newindex].h-2);
						//ReOpen(newindex,children[i].g,children[i].PrevMove);
					}

				//---*********** this part worked ********************---
				//if(old[newindex].g>children[i].g)
				//{
				//	old[newindex].g=children[i].g;
				//	boo=false;
				//	if(old[newindex].h<children[i].h)
				//		old[newindex].h=children[i].h;
				//	ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//}
				//else //(g in close is lower than g in children)
				//{
				//	if(old[newindex].g==children[i].g)
				//	{
				//	if(old[newindex].h<children[i].h)
				//	{
				//		boo=false;
				//		old[newindex].h=children[i].h;
				//		ReOpen(newindex,old[newindex].g,children[i].PrevMove);
				//	}
				//	}
				//}//---*********** this part worked ********************---
				}
	}//end if (for existing child)
			else
				boo=0;
		//boo=true; //for testing
		if (boo==0) 
		{
			//printf("%s\n","adding the child");
			children[i].add2Open=true;
		}
		if(boo==1)
		{
			//printf("%s\n","NOT adding the child");
			children[i].add2Open=false;
		}
		if(boo==2)
		{
			ReOpen(newindex,children[i].g,children[i].PrevMove);
			children[i].add2Open=false;
		}

		}
	//string mystr;
	//getline (cin,mystr);
	}//end for

	// Now we can add the children to the OPEN list
	for (int i=0;i<ChildNum;i++)
	{
		if(children[i].add2Open)
		{
			hashval=CalcHash(children[i].boardState);
			if(children[i].h+children[i].g<UpperLimit)
			{
			//if(children[i].h+children[i].g>old[heap[0]].g+old[heap[0]].h)
			if(children[i].h+children[i].g>NextBestF) 
			{
				InsertHash2(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
			}
			else
			{
				int hashindex=Add2Close(children[i].boardState,hashval,children[i].PrevMove,children[i].g,children[i].h);
				IE++;
				if(children[i].h+children[i].g<=lookahead)
					ILHBPMXExpand(hashindex,children[i].g,children[i].h,lookahead,children[i].PrevMove);
			}

			}
		}
	}//end for
	old[stateIndex].h=MAX(old[stateIndex].h,maxH-1);

return -1;

}

void BPMXLHAStar1(short s[SIZE],int lookahead)
{
		//Variables
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;


	//srand ( (unsigned)time ( NULL ) );
	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}
	for (int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	NextBestF=0;
	NextBestC=0;
	LHnodes=0;
	BUpdate=0;
	LHUpdate=0;
	BLHUpdate=0;
	IGSameV=0;
//	UCount=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	 old[empty].cost=bestf;
	empty++;
	heap[0]=0;
	CostArr[bestf]=1;

	while (CurrentDepth!=100 && old[heap[0]].cost<UpperLimit && stored <FULL_OPEN && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		NextBestC=INFINITY;
		if(OpenStart>1 )
		{
			NextBestC=old[heap[0]].cost+1;
			while(CostArr[NextBestC]==-1&& NextBestC<40)
				NextBestC++;
		}
		CurrentOpenNode=heap[0];
		//printf("%s %d %s %d %s %d\n","eh=",old[CurrentOpenNode].h," eg=",old[CurrentOpenNode].g,"ec=",old[CurrentOpenNode].cost);
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		NextBestF=old[CurrentOpenNode].h+old[CurrentOpenNode].g;
	
		int ActualLH=MIN(NextBestF+lookahead,NextBestC);
		if(ActualLH<bestc)
		{
			ActualLH=-1;
		}
		ActualLH=MIN(ActualLH,UpperLimit);

		CurrentDepth=IIBExpandNodeLH(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,ActualLH);
		
		expanded++;
	}
	printf("%s %d %s %d\n","heap[0].h=",old[heap[CurrentOpenNode]].h," heap[0].g=",old[heap[CurrentOpenNode]].g);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	//PrintResult2File("AStartLH",lookahead);
	PrintResult("AL*(%d) with BPMX(op.1)",lookahead);
	printf("%s\n","");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
    printf("%s %d %s %d %s %d %s %d %s %d\n","LHnodes=",LHnodes,"BUpdate=",BUpdate,"LHUpdate=",LHUpdate,"BLHUpdate=",BLHUpdate,"IGSameV=",IGSameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}





void BPMXLHAStar2(short s[SIZE],int lookahead)
{
	//Variables
	int CurrentHashValue;
	int CurrentDepth;
	int CurrentOpenNode; //next node in the open list to check
	double startclock;
	double endclock;

	//srand ( (unsigned)time ( NULL ) );
	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}
	for (int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	CurrentOpenNode=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	NextBestF=0;
	NextBestC=0;
	LHnodes=0;
	BUpdate=0;
	LHUpdate=0;
	BLHUpdate=0;
	IGSameV=0;
//	UCount=0;

	//Init goal test inidicator
	CurrentDepth=0;
	//duplicateFlag = 1;
	duplicatCounter=0;
	goalDepth=0;
		//Start counting time
	startclock = (double)clock();
	CurrentHashValue=CalcHash(s);
	//Insert the initial state to the hash table and update the open list
	for (int word = 0;word<SIZE;word++)
		old[empty].boardState[word]=s[word];
	old[empty].PrevMove = SIZE;
	old[empty].g = 0;
	ConvertStateToDual(0);
	old[empty].h=bestf=GetHuristicRegular(DualState);
	old[empty].link = bucket[CurrentHashValue];      /* next pointer to old first element */
	old[empty].heaplink=0;
	 bucket[CurrentHashValue] = empty;               /* new state is at head of hash chain */
	 int f = old[empty].g + old[empty].h; 
	 old[empty].cost=bestf;
	empty++;
	heap[0]=0;
	CostArr[bestf]=1;
	//HBLookahead3(0,0,bestf,bestf+lookahead,SIZE);
	//printf("%s %d\n","f=",old[0].h);

	//BLookahead(0,old[heap[0]].g,old[heap[0]].h,old[heap[0]].g+lookahead,old[heap[0]].PrevMove);
	//printf("%d\n",bestf);
	while (CurrentDepth!=100 && old[heap[0]].cost<UpperLimit && stored <FULL_OPEN && OpenStart>=0)
	{
		bestf=old[heap[0]].h+old[heap[0]].g;
		bestc=old[heap[0]].cost;
		NextBestC=INFINITY;
		if(OpenStart>1 )
		{
			NextBestC=old[heap[0]].cost+1;
			while(CostArr[NextBestC]==-1&& NextBestC<40)
				NextBestC++;
		}
		CurrentOpenNode=heap[0];
		FDeleteFromOpenList(CurrentOpenNode); //delete the node expanded from the open list
		NextBestF=old[CurrentOpenNode].h+old[CurrentOpenNode].g;
	
		int ActualLH=MIN(NextBestF+lookahead,NextBestC);
		if(bestc>ActualLH) 
			ActualLH=-1;

		ActualLH=MIN(ActualLH,UpperLimit);
		CurrentDepth=IIBExpandNodeLH2(CurrentOpenNode,old[CurrentOpenNode].g,old[CurrentOpenNode].h,old[CurrentOpenNode].PrevMove,ActualLH);
		expanded++;
		//printf("%s %d\n","IG=",ImmediateGenerated);

	}
			//string mystr;
		//getline (cin,mystr);
	goalDepth=UpperLimit;
	endclock = (double)clock();
	printf("%s %d %s %d\n","heap[0].h=",old[heap[CurrentOpenNode]].h," heap[0].g=",old[heap[CurrentOpenNode]].g);
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	//PrintResult2File("AStartLH",lookahead);
	PrintResult("AL* with BPMX(op.2)",lookahead);
	printf("%s\n","");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
	printf("%s %d %s %d %s %d %s %d %s %d\n","LHnodes=",LHnodes,"BUpdate=",BUpdate,"LHUpdate=",LHUpdate,"BLHUpdate=",BLHUpdate,"IGSameV=",IGSameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}


/**
 An IDA* iteration. Input is the g and h of the root node, 
 the threshold value for this iterations (nodes over the threshold will not be expanded)
 and the previous move (to avoid simple cycles).
 Returns: A proposed h for the parent (BPMX)
 Updates: minf with the minimum frontier f-value
          UpperBound with new (minimal) cost of goal
 **/
int globalMinNextThresh;
int IDAStarWithBPMXIteration(short state[SIZE],int g, int h, int threshhold,int prevMove)
{
	int newg;
	int newh;
	int resultMinF;
	int maxH;
	int f=g+h;

	maxH=0;

	if((f>threshhold)||(f>=UpperLimit)){ // If over the threshold
		if (f<globalMinNextThresh)
			globalMinNextThresh=f;
		return h;
	}

	if ((h==0) && (IsGoal(state))) // If is goal
	{
		if (g<UpperLimit) 
			UpperLimit=g;
		
		if (f<globalMinNextThresh)
			globalMinNextThresh=f;
		return h;
	}

	// If not goal and under threshold - expand
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		++expanded;
		if (prevMove==newMove)// 0 -> 4 -> 8
			continue;

		MakeMove(state,newMove); //generate a child

        ImmediateGenerated++;

		ConvertStateToDual(state);
		newh=GetHuristicRegular(DualState); //calculate child h
		newh=MAX(h-1,newh); // BPMX parent to child
	    newh=IDAStarWithBPMXIteration(state,newg,newh,threshhold,newMove);
		h=MAX(h,newh-1); // BPMX child to parent
		MakeMove(state,newMove); // undo
		f=g+h;
		if((f>threshhold)||(f>=UpperLimit)){ // If over the threshold
			if (f<globalMinNextThresh)
				globalMinNextThresh=f;
			return h;
		}
	}//end for
	return h;
}//End BLookahead



/**
 An IDA* iteration. Input is the g and h of the root node, 
 the threshold value for this iterations (nodes over the threshold will not be expanded)
 and the previous move (to avoid simple cycles).
 Returns: The minimum f that exceeded the threshold or found a goal
 Updates: minf with the minimum frontier f-value
          UpperBound with new (minimal) cost of goal
 **/
int IDAStarIteration(short state[SIZE],int g, int h, int threshhold,int prevMove)
{
	int newg;
	int newh;
	int maxH;
	int f=g+h;
	maxH=0;

	if((f>threshhold)||(f>=UpperLimit)){ // If over the threshold
		if (f<globalMinNextThresh){
			globalMinNextThresh=f;
		}
		return h;
	}

	if ((h==0) && (IsGoal(state))) // If is goal
	{
		if (g<UpperLimit) 
			UpperLimit=g;
		if (f<globalMinNextThresh){
			globalMinNextThresh=f;
		}
		return h;
	}

	// If not goal and under threshold - expand
	newg=g+1; // calculate child g
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		++expanded;
		if (prevMove==newMove)// 0 -> 4 -> 8
			continue;

		MakeMove(state,newMove); //generate a child

        ImmediateGenerated++;

		ConvertStateToDual(state);
		newh=GetHuristicRegular(DualState); //calculate child h
		newh=MAX(h-1,newh); // Pathmax first rule
	    IDAStarIteration(state,newg,newh,threshhold,newMove); // Possibly updating globalMinNextThresh
		MakeMove(state,newMove); // undo
	}//end for
	return h;
}//End BLookahead


/**
	Sets up global variables for the search
 **/
void setupSearch(){
	//Init Hash table
	for (int i = 0; i< MAX_HASH; i++)                    /* empty hash table */
    {
		old[i].g = -1;                  /* only g value checked for emptiness */
		old[i].heaplink=-1;
		bucket[i] = MAX_HASH;
		for (int k=0;k<SIZE;k++)
			old[i].boardState[k]=-1;
	}

	for (int t=0;t<FULL_OPEN;t++)
	{
		heap[t]=-1;
	}
	for (int i=0;i<40;i++)
		CostArr[i]=-1;


	//Init Open List pointers
	OpenStart=0; // beginning of the open list
	OpenEnd = 0; //End of the open list

	//Init next free loaction index in hash table
	empty=0;

	//Init counters
	maxopen=0;
	copen=0;
	expanded=0;                               
	generated=0;                             
	stored=0;
	reopened=0;
	opened=0;
	closed=0;
	ImmediateGenerated=0;
	IE=0;
	UpperLimit=1101; //TODO - need to find logical upper limit
	FoundInC=0;
	FoundInO=0;
	NextBestF=0;
	NextBestC=0;
	LHnodes=0;
	BUpdate=0;
	LHUpdate=0;
	BLHUpdate=0;
	IGSameV=0;

	//Init goal test inidicator
	duplicatCounter=0;
	goalDepth=0;
}

/**
 Run the classic IDA*
 **/
void ClassicIDAStar(char* algorithmName, short state[SIZE],int (*iterationFunction)(short[SIZE],int,int,int,int))
{
		//Variables
	int CurrentHashValue;
	int CurrentDepth=0;
	int CurrentOpenNode=0; //next node in the open list to check
	double startclock;
	double endclock;
	
	setupSearch();

	//Start counting time
	startclock = (double)clock();

	ConvertStateToDual(state);
	int h=GetHuristicRegular(DualState); //calculate child h
	int threshold=1;
	while(UpperLimit>threshold){
		globalMinNextThresh=INFINITY;
		iterationFunction(state,0,h,threshold,0); // updating globalMinNextThresh
		threshold=globalMinNextThresh;
		if(DEBUG_PRINTS)
			printf("Threshhold %d, Expanded so far %d\n", threshold,expanded);
	}

	goalDepth=UpperLimit;
	endclock = (double)clock();
	time2search = (endclock-startclock)/(double)CLOCKS_PER_SEC;
	//PrintResult2File("AStartLH",lookahead);
	PrintResult(algorithmName);
	printf("%s\n","");
	printf("%s","expanded= ");
	printf("%d \n",expanded);
	printf("%s","IE= ");
	printf("%d \n",IE);
	printf("%s","stored = ");
	printf("%d \n",stored);
		printf("%s","reopened = ");
	printf("%d \n",reopened);
		printf("%s","IG= ");
	printf("%d \n",ImmediateGenerated);
	printf("%s","opened = ");
		printf("%d \n",opened);
	printf("%s","closed = ");
	printf("%d \n",closed);
	printf("%s %d\n","maxopen = ",maxopen);
	printf("%s","goalDepth = ");
	printf("%d \n",goalDepth);
	printf("%s", "Start Time = ");
	printf ("%f \n",startclock);
	printf("%s", "Stop Time = ");
	printf ("%f \n",endclock);
    printf("%s %d %s %d %s %d %s %d %s %d\n","LHnodes=",LHnodes,"BUpdate=",BUpdate,"LHUpdate=",LHUpdate,"BLHUpdate=",BLHUpdate,"IGSameV=",IGSameV);
	printf("%s", "time2search = ");
	printf ("%f \n",time2search);

}

void runAlgorithms(short tempState[SIZE])
{
	int oldGoalDepth;
	printf("%s","--------- ");
	printf("%d %s\n",CaseCounter,"--------------");
	for(int k=0;k<SIZE;k++)
			printf("%d ",tempState[k]);
	printf("%s\n","");
	printf("%s\n","======");

	printf("======IA+BPMX(1) [%d] =====\n",CaseCounter);
	PerformTrivial=true;
	UseInconsistency=true;
	IBPMXAStar(tempState,"IA*+BPMX");
	oldGoalDepth=goalDepth;
	printf("======A+BPMX(1) [%d] =====\n",CaseCounter);
	PerformTrivial=false;
	UseInconsistency=true;
	BPMXAStar(tempState);
	if (goalDepth!=oldGoalDepth)
	{
		printf("Problem %d,%d",goalDepth,oldGoalDepth);
		exit(0);
	}

	UseInconsistency=true;
	for(int i=0;i<4;i++){
		printf("======AL(%d)+BPMX [%d] =====\n",i,CaseCounter);
		BPMXLHAStar1(tempState,i);
		BPMXLHAStar2(tempState,i);		
	}

	printf("======IDA* with BPMX[%d] =====\n",CaseCounter);
	UseInconsistency=true;
	ClassicIDAStar("IDA* with BPMX",tempState,IDAStarWithBPMXIteration);
	if (goalDepth!=oldGoalDepth)
	{
		printf("Problem %d,%d",goalDepth,oldGoalDepth);
		exit(0);
	}

	printf("======A* Inconsistent[%d] =====\n",CaseCounter);
	UseInconsistency=true;
	ClassicAStar(tempState,"A* Inconsistent");

	printf("======IDA* [%d] =====\n",CaseCounter);
	UseInconsistency=false;
	ClassicIDAStar("IDA*",tempState,IDAStarIteration);
	if (goalDepth!=oldGoalDepth)
	{
		printf("Problem %d,%d",goalDepth,oldGoalDepth);
		exit(0);
	}


	UseInconsistency=false;
	for(int i=0;i<4;i++){
		printf("======LA*(%d) [%d] =====\n",i,CaseCounter);
		LHAStar2(tempState,i);
	}
	printf("======A* [%d] =====\n",CaseCounter);
	UseInconsistency=false;
	ClassicAStar(tempState,"A*");

	printf("======IA* [%d] =====\n",CaseCounter);
	UseInconsistency=false;
	IClassicAStar(tempState,0);

}



//---------------------- MAIN --------------------------
void main2(int argc, char *argv[],bool ignoreSomeCases)
{
	
	FILE *states_ptr;

	//Init tables
	initHashPow();
	InitPDB();
	InitPDBParameters();
	for(int i=0;i<SIZE;i++)
		printf("%d ",arrPatternLocation[i]);
	printf("%s\n","");

	//Init counters
	CaseCounter=0;

	states_ptr=fopen(ProblemsFile,"r");
    if (states_ptr==NULL){printf ("ProblemsFile not found or File can not be opened\n"); exit(0);}
	//Run search

	//ClassicAStar(s1);
	//ClassicAStar(s3);
	//ClassicAStar(s15);
	short tempState[SIZE];
	//BPMXLHAStar(s0,2);
	while(!feof(states_ptr) && CaseCounter<100)
	{

		CaseCounter++;

		fscanf(states_ptr,"%*d"); 
		for(int i=0;i<SIZE;i++)
			fscanf(states_ptr,"%d",&tempState[i]);
		if (ignoreSomeCases){
			if(CaseCounter==9 || CaseCounter==11 || CaseCounter==19 || CaseCounter==20 || CaseCounter==25 || CaseCounter==28 || CaseCounter==30|| CaseCounter==38 || CaseCounter==40 || CaseCounter==41 || CaseCounter==43 || CaseCounter==45 || CaseCounter==50 || CaseCounter==51 || CaseCounter==54)
		   // if(CaseCounter==41 || CaseCounter==43 || CaseCounter==45 || CaseCounter==50 || CaseCounter==51 || CaseCounter==54)
		  // if( CaseCounter==43)
			{
				runAlgorithms(tempState);
			}
		}
		else{
			runAlgorithms(tempState);
		}
	}
	printf("--------------- FINISHED! -----------------\n");
}



void main(int argc, char *argv[])
{
	//main2(argc,argv,true);
	main2(argc,argv,false);
	printf("--------------- FINISHED! -----------------\n");
}








